/*
============================================================================
 Name        : dd_btree.h
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_btree.h - header file
============================================================================
*/

#ifndef DD_BTREE_H
#define DD_BTREE_H


#include "dd_define.h"


__DD_BEGIN_DECLS


/* 
 * The M(>=3) grade B-Tree(2-3-4 tree) Implement 
*/

typedef void					dd_btree_key ;
typedef void					dd_btree_value ;
typedef struct __dd_btree_node	dd_btree_node ;
typedef struct __dd_btree		dd_btree ;


struct __dd_btree_node {

	DD_INT			child_count ;
	
	union {
		dd_btree_node**	children ;
		dd_btree_value*	leaf_value ;
	} data;
	
	dd_btree_key*	key ;	
};


struct __dd_btree {
	DD_INT M ;  /* M must is bigger than 2 */
    dd_btree_node*	root ;
	DD_INT (*key_compare)(const dd_btree_key* key1, const dd_btree_key* key2) ;	/* 0: equal ; -1: key1 < key2 ; 1: key1 > key2 */
	void (*key_conflict)(dd_btree_key* key_found_conflict, dd_btree_value* value_found_conflict, dd_btree_key* key_handle, dd_btree_value* value_handle) ;
};


/* Interfaces */

dd_btree* dd_btree_create(
    DD_INT M,
	DD_INT (*key_compare)(const dd_btree_key*, const dd_btree_key*), 
	void (*key_conflict)(dd_btree_key* , dd_btree_value*, dd_btree_key*, dd_btree_value*) 
) ;

void dd_btree_destroy(dd_btree* btree) ;

dd_btree_value* dd_btree_find(const dd_btree* btree, dd_btree_key* key) ;

void dd_btree_insert(dd_btree* btree, dd_btree_key* key, dd_btree_value* value) ;

dd_btree_value* dd_btree_remove(dd_btree* btree, dd_btree_key* key) ;


#ifdef __DD_UNITTEST

DD_BOOL dd_btree_test() ;

#endif


__DD_END_DECLS


#endif	/* DD_BTREE_H */

/* End of File */
